//
// Created by LiuYou on 2021/11/28.
//

#include <iostream>
#include <vector>
#include <iterator>


/**
 * @brief 交换 arr 的 两个位置上的元素。
 * @param arr 原始内置数组。
 * @param lhs 要交换的两个位置中的一个。
 * @param rhs 要交换的两个位置中的另一个。
 *
 * @details 采用了异或位运算。
 * <p> ^ 即异或运算。
 * 两个位不同为 1, 相同为 0。</p>
 *
 * <p> 1 ^ 1 = 0</p>
 * <p> 0 ^ 0 = 0</p>
 * <p> 1 ^ 0 = 1</p>
 * <p> 0 ^ 1 = 1</p>
 *
 * 再例如:
 * <p>a: 1 0110, b: 0 0111。</p>
 * <p>a: 1 0110</p>
 * <p>b: 0 0111</p>
 * <p>a ^ b = 1 0001</p>
 *
 * 异或运算可以看为是无进位相加。
 *
 * 异或运算有哪些性质:
 * 1>
 * 0 ^ n = n
 * n ^ n = 0
 *
 * 2> 异或运算满足交换律和结合律。
 * a ^ b = b ^ a
 * a ^ b ^ c = a ^ (b ^ c)
 *
 * 3> 同样一批数, 异或的结果与哪两个数先异或无关。同一批数异或的结果是一样的。
 *
 * @note 这个函数的中只有 3 行代码, 但是就是只需要这三行代码就能完成两个数的交换。
 * 但是注意: 要交换的两个元素是相同的值也没有关系。但是要交换的两个元素在内存中必须是两块独立的空间。
 *
 * @note 参数 lhs 和 参数 rhs 不能是相同的位置。
 * 如果 lhs 与 rhs 相同的话, 就是同样一块内存在跟自己异或,
 * 内存会洗成 0 的！即 0 ^ 0 = 0, 1 ^ 1 = 0, n ^ n = 0。
 *
 * FIXME: 最后的还有一个问题: 异或的是元素的地址还是元素的内存?
 *
 */
static void swap(int arr[], int lhs, int rhs) {
    arr[lhs] = arr[lhs] ^ arr[rhs];
    arr[rhs] = arr[lhs] ^ arr[rhs];
    arr[lhs] = arr[lhs] ^ arr[rhs];
}


/**
 * @brief 冒泡排序。
 * @param arr 需要排序的数组。
 *
 * @details 注意: 在写这个算法的时候, 数组下标边界时一定要仔细考虑好。
 * 因为很容易出错。
 */
static void bubbleSort(std::vector<int>& arr) {
    if (arr.empty() || arr.size() < 2) {
        return;
    }

    // 0 ~ i
    // 第一个循环指的是: 我要在 0 ~ i 的位置上, 相邻两个数交换。
    // 然后循环结束后, 我继续在 0 ~ i-1 的位置上, 相邻两个数交换。
    // ...
    for (int i = arr.size() - 1; i > 0; --i) {
        // 第二个for循环指的是: j 从 0 出发, j < i。
        // 每次对比后一个数是否比前一个数大。
        // 如果有那就交换。
        for (int j = 0; j < i; ++j) {
            if (arr[j] > arr[j + 1]) {
//                std::swap( arr[j], arr[j + 1] );
                swap( arr.data(), j, j + 1 );
            }
        }
    }
}


int main(int argc, char** argv) {
    std::vector<int> arr{99, 35, 2, 111, 35, 96, 352};

    {
        bubbleSort( arr );
        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, " " ));
    }


    return 0;
}
